package JavaSE;
import java.util.Arrays;
import java.util.Scanner;
//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：[3,2,3]
//输出：3
//示例 2：
//输入：[2,2,1,1,1,2,2]
//输出：2
public class time_2025_07_18找出数组中出现次数大于二分之length的元素 {
    public static int majorityElement(int[] nums){
        int count = 0;
        int candidate = 0;
        for(int i = 0;i < nums.length;i++) {
            count = 1; // 重置计数器
            candidate = nums[i];
            for (int j = i+1; j <= nums.length-1; j++) {
                if(candidate == nums[j]){
                    count++;
                }
            }
            if(count >= nums.length / 2) {
                return candidate;
            }
        }
        return -1; // 如果没有找到符合条件的元素，返回-1
    }

    public static int majorityElement2(int[] nums){
        int count = 0;
        int candidate = 0;
        for(int num:nums){
            if(count==0){
                candidate = num;
            }
            count += (num == candidate)?1:-1;
        }
        return candidate;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入数组的长度: ");
        int length = scanner.nextInt();
        int[] nums = new int[length];
        System.out.print("请输入数组的元素: ");
        for(int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        int result = majorityElement(nums);
        if(result != -1) {
            System.out.println("数组中出现次数大于二分之length的元素是: " + result);
        } else {
            System.out.println("没有找到符合条件的元素。");
        }

        int result2 = majorityElement2(nums);
        System.out.println(result2);
    }
}
